NScale: Neighborhood-centric Large-Scale Graph Analytics in the Cloud

摘要

There is an increasing interest in executing complex analyses over largegraphs, many of which require processing a large number of multi-hopneighborhoods or subgraphs. Examples include ego network analysis, motifcounting, personalized recommendations, and others. These tasks are not wellserved by existing vertex-centric graph processing frameworks, where userprograms are only able to directly access the state of a single vertex. Thispaper introduces NSCALE, a novel end-to-end graph processing framework thatenables the distributed execution of complex subgraph-centric analytics overlarge-scale graphs in the cloud. NSCALE enables users to write programs at thelevel of subgraphs rather than at the level of vertices. Unlike most previousgraph processing frameworks, which apply the user program to the entire graph,NSCALE allows users to declaratively specify subgraphs of interest. Ourframework includes a novel graph extraction and packing (GEP) module thatutilizes a cost-based optimizer to partition and pack the subgraphs of interestinto memory on as few machines as possible. The distributed execution enginethen takes over and runs the user program in parallel, while respecting thescope of the various subgraphs. Our experimental results showorders-of-magnitude improvements in performance and drastic reductions in thecost of analytics compared to vertex-centric approaches.